package hero.mps.leet_code_15;

import java.util.*;

public class Sum3 {
    public static List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        int component = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < nums.length ; j++) {
                component = - nums[i] - nums[j];
                if (map.containsKey(component)) {
                    Integer[] temp = new Integer[]{nums[i], nums[j], component};
                    Arrays.sort(temp);
                    res.add(Arrays.asList(temp));
                }
                map.put(nums[j], j);
            }

        }
        return new ArrayList<>(res);
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        // 对数组进行排序
        Arrays.sort(nums);
        // 创建一个结果列表，用于存储所有可能的三元组
        List<List<Integer>> res = new LinkedList<>();
        // 遍历数组，从第一个元素开始，直到倒数第三个元素
        for (int i = 0; i < nums.length - 2; i++) {
            // 如果当前元素大于0，则不可能再找到满足条件的三元组，直接跳出循环
            if (nums[i] > 0) break;
            // 如果当前元素是第一个元素或者当前元素与前一个元素不相等
            if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
                // 初始化左指针和右指针，以及目标和为当前元素的相反数
                int left = i + 1, right = nums.length - 1, sum = 0 - nums[i];
                // 当左指针小于右指针时，执行循环
                while (left < right) {
                    // 如果左指针和右指针指向的元素之和等于目标和
                    if (nums[left] + nums[right] == sum) {
                        // 将满足条件的三元组添加到结果列表中
                        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        // 跳过左指针指向的重复元素
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        // 跳过右指针指向的重复元素
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        // 左指针右移
                        left++;
                        // 右指针左移
                        right--;
                    // 如果左指针和右指针指向的元素之和小于目标和
                    } else if (nums[left] + nums[right] < sum) {
                        // 左指针右移
                        left++;
                    } else {
                        // 右指针左移
                        right--;
                    }
                }
            }
        }
        // 返回结果列表
        return res;

    }
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> res = threeSum1(nums);
        System.out.println(res);
    }
}
